Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 10
з дисципліни: “Об’єктно-орієнтоване програмування”
на тему: “Стандартні бібліотеки. Класи, контейнери, ітератори, алгоритми”
Мета лабораторної роботи
Познайомитися зі стандартними бібліотеками, класами, ітераторами, алгоритмами.
Теоретичні відомості
Стандартна бібліотека шаблонів
Стандартна бібліотека шаблонів (Standard Template Library – STL) входить у стандартну бібліотеку мови C++. Уся бібліотека побудована на шаблонах класів і функцій, що забезпечує можливість уніфікованої роботи з різними типами даних. Використання шаблонів у бібліотеці дозволяє не тільки однаково обробляти вбудовані типи С++, але й працювати з користувацькими типами даних, що не були відомі в момент розробки бібліотеки.
Якщо більш конкретно розглянути склад STL, то в ній можна виділити наступні компоненти:
Контейнери (contaіners) – це класи, призначені для зберігання сукупностей об’єктів (як вбудованих, так і визначених користувачем типів). Найпростіші види контейнерів (статичні і динамічні масиви) вбудовані безпосередньо в мову C++.
Ітератори (іterators) – це абстракція покажчика, тобто об'єкт, що може посилатися на інші об'єкти, що містяться в контейнері. Основні функції ітератора – забезпечення доступу до об'єкта, на який він посилається (розіменування), і перехід від одного елемента контейнера до іншого (ітерація, звідси і назва ітератора). Для вбудованих контейнерів у якості ітераторів використовуються звичайні вказівники. У випадку з більш складними контейнерами ітератори реалізуються у виді класів з набором перевантажених операторів.
Алгоритми (algorіthms) – це функції для маніпулювання об'єктами, що містяться в контейнері. Типові приклади алгоритмів – сортування та пошук. У STL реалізовано порядку 60 алгоритмів, які можна застосовувати до різних контейнерів, у тому числі до масивів, вбудованим у мову C++.
Контейнери
У наступній таблиці приведені основні класи контейнерів бібліотеки STL.
Як уже зазначалось, контейнер призначений для збереження об'єктів. Хоча внутрішня організація контейнерів дуже сильно відрізняється, кожен контейнер зобов'язаний надати строго визначений інтерфейс, через який з ним будуть взаємодіяти алгоритми. Цей інтерфейс забезпечують ітератори. Кожен контейнер зобов'язаний мати відповідний йому ітератор. Важливо підкреслити, що жодні додаткові функції-члени для взаємодії алгоритмів і контейнерів не використовуються. Це зроблено тому, що стандартні алгоритми повинні працювати в тому числі з вбудованими контейнерами мови C++, у яких є ітератори (вказівники), але немає нічого, крім них. Власне тому при написанні власного контейнера реалізація ітератора – необхідний мінімум.
Кожен контейнер реалізує визначений тип ітераторів. При цьому вибирається найбільш функціональний тип ітератора, що може бути ефективно реалізований для даного контейнера. "Ефективно" означає, що швидкість виконання операцій над ітератором не повинна залежати від кількості елементів у контейнері. Наприклад, для вектора реалізується ітератор з довільним доступом, а для списку – двонаправлений. Оскільки швидкість виконання операції [] для списку лінійно залежить від його довжини, ітератор з довільним доступом для списку не реалізується.
Тип контейнера
Клас контейнера
Деректива #include
Послідовні контейнери
(Sequence containers)
vector – масиви
< vector >
deque – двостороння черга
<deque>
lіst – списки
< lіst>
Асоціативні контейнери
(Associative containers)
map, multіmap – карти; це структури, подібні до масиву, але в яких роль "індексу" можуть відігравати не тільки цілі числа, але будь-які упорядковані типи
<map>
set, multіset – множини
<set>
bitset – множини як бітові набори
<bitset>
Адаптори
(Container adaptors)
queue – черги, організовані за принципом FIFO
priority queue – пріоритетні черги
<queue>
stack – стеки, організовані за принципом LIFO
<stack>
Незалежно від фактичної ...